package com.chenxys.algorithm.newbie;

import com.chenxys.algorithm.common.ListNode;

/**
 * <p>
 *      给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。<br/>
 *      请你将两个数相加，并以相同形式返回一个表示和的链表。<br/>
 *      你可以假设除了数字 0 之外，这两个数都不会以 0 开头。<br/>
 *      示例： <br/>
 *          链表1: 2 -> 4 -> 3  == 342<br/>
 *          链表2: 5 -> 6 -> 4  == 465<br/>
 *          返回 : 7 -> 0 -> 8  == 807 <br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/30/23 3:20 PM
 * @Copyright ©
 */
public class AddTwoNumbers {

    /**
     * <p>
     *     求链表长度
     * </p>
     * @param head 链表
     * @return 链表长度
     */
    public static int listLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    /**
     * <p>
     *     两个链表相加,返回求和后的链表
     * </p>
     * @param l1 链表1
     * @param l2 链表2
     * @return 求和后链表
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = listLength(l1);
        int len2 = listLength(l2);
        ListNode l = len1 >= len2 ? l1 : l2;
        ListNode s = l == l1 ? l2 : l1;
        ListNode curL = l;
        ListNode curS = s;
        ListNode last = curL;
        int carry = 0;
        int curNum = 0;
        while (curS != null) {
            curNum = curL.val + curS.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
            curS = curS.next;
        }

        while (curL != null){
            curNum = curL.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }

        if (carry != 0) last.next = new ListNode(carry);
        return l;
    }
}
